#include "LRUCache.hpp"

template <typename Key, typename Value>
class LRU_K_Cache : public LRUCache<Key, Value>
{
public:
    LRU_K_Cache(int capacity, int k, int histroyCapacity) : LRUCache<Key, Value>(capacity), m_k(k)
    , histroyList(std::make_unique<LRUCache<Key, size_t>>(histroyCapacity))
    {}

    void put(const Key& key, const Value& value)
    {
        // 先在主缓存中查找，如果存在，则更新
        Value v;
        bool inMain = LRUCache<Key, Value>::get(key, v);
        if (inMain)
        {
            // 更新主缓存
            LRUCache<Key, Value>::put(key, value);
            return;
        }
        histroyValue[key] = value;
        size_t count = histroyList->get(key);
        histroyList->put(key, ++count);
        // 如果访问次数达到
        if (count == m_k)
        {
            LRUCache<Key, Value>::put(key, value);
            histroyList->remove(key);
            histroyValue.erase(key);
        }
    }

    Value get(const Key& key)
    {
        // 先在主缓存中查找，如果存在，则更新
        Value value{};
        bool inMain = LRUCache<Key, Value>::get(key, value);
        if (inMain)
        {
            return value;
        }
        auto it = histroyValue.find(key);
        if (it == histroyValue.end())
        {
            return Value();
        }
        size_t count = histroyList->get(key);
        histroyList->put(key, ++count);
        // 如果访问次数达到
        if (count == m_k)
        {
            LRUCache<Key, Value>::put(key, it->second);
            histroyList->remove(key);
            histroyValue.erase(it);
        }
        return it->second;
    }
private:
    int m_k;
    std::unique_ptr<LRUCache<Key, size_t>> histroyList;
    std::unordered_map<Key, Value> histroyValue;
};